#include <stdio.h>
#include <malloc.h>

struct node {
	struct node *left;
	struct node *right;
	int val;
};

struct node *head;

struct node *alloc_node(int val)
{
	struct node *p = malloc(sizeof(*p));
	p->val = val;
	p->left = p->right = NULL;

	return p;
}

void insert(struct node *node, int val)
{
	if (val < node->val) {
		if (node->left)
			insert(node->left, val);
		else {
			node->left = alloc_node(val);
			return;
		}
	} else {
		if (node->right)
			insert(node->right, val);
		else {
			node->right = alloc_node(val);
			return;
		}
	}
}

void inorder(struct node *node, int level)
{
	if (!node)
		return;

	inorder(node->left, level + 1);
	printf("%d: %d\n", level, node->val);
	inorder(node->right, level + 1);
}

void preorder(struct node *node, int level)
{
	if (!node)
		return;

	printf("%d: %d\n", level, node->val);
	preorder(node->left, level + 1);
	preorder(node->right, level + 1);
}

int main(void)
{
	head = alloc_node(10);

	insert(head, 5);
	insert(head, 7);
	insert(head, 9);
	insert(head, 11);
	insert(head, 3);
	insert(head, 2);
	insert(head, 6);
	insert(head, 1);

	inorder(head, 0);
	printf("\n");
	preorder(head, 0);
	printf("\n");

	return 0;
}

